package com.leetcode.背包问题;

import java.util.Arrays;

/**
 * 01背包：每件物品只取一次
 * N件物品，背包容量为 W，第i件物品的重量是weight[i],价值是value[i]
 * 在装的物品容量不超过 W的情况下，如何使得到的价值最大？
 */
public class BagProblem {
    static int[][] dp = new int[3][5];
    static int[] weight = new int[]{1,3,4};
    static int[] value = new int[]{15,20,30};
    public static void main(String[] args) {
        getMaxValue2(weight,value,3,4);
        for (int i = 0; i < 3; i++) {
            System.out.println(Arrays.toString(dp[i]));
        }
        getMaxValue1(weight,value,3,4);
    }

    /**
     * 利用二维dp数组
     * @param weight
     * @param value
     */
    public static void getMaxValue2(int[] weight,int[] value,int N,int W){
        /**
         * 1.定义dp[i][j]:下标[0,i]的物品 任取 若干个放在容量为j的背包，价值最大为dp[i][j]
         * 2.递推关系，dp[i][j]有两种情况得来：（放 或 没放，单独分析时都是 确定情况）
         * ①：若物品i不放（确定没放），则dp[i][j]的值就等于dp[i - 1][j]，表示i没放的情况下，前面i - 1个任取若干个
         * ②：若物品i放（确定放置），则背包此时剩余容量为 j - weight[i]
         *    在此容量下，让前面i - 1个任取若干个使价值最大，就是为 dp[i - 1][j - weight[i]]，再加上i的价值
         * 因此，dp[i][j] = Math.max(dp[i - 1][j] , dp[i - 1][j - weight[i]] + value[i])
         * 3.初始化
         * 当j为0时，表示背包容量为0，则不管怎么放价值都为0，即dp[i][0] = 0
         * 由公示可以推出，i是由i - 1推导而来，则i为0时，必须初始化！
         * ①：当j<weight[0]时，dp[0][j] = 0
         * ②：当j >= weight[0]时，dp[0][j] = weight[0]
         * 4.遍历顺序（画出dp更容易理解）
         *  可以先遍历i再遍历j，也可以先遍历j再遍历i，无影响（一维dp需要注意）
         */
//        int[][] dp = new int[N][W + 1];//为了能够访问到dp[i][W]
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < (W + 1); j++) {
                if(j == 0){
                    dp[i][j] = 0;//初始化
                } else if(i == 0){
                    dp[i][j] = j < weight[0] ? 0 : value[0];//初始化
                } else{
                    dp[i][j] = dp[i - 1][j];
                    if (j - weight[i] >= 0){
                        dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - weight[i]] + value[i]);
                    }
                }
            }
        }
//        return dp[N - 1][W];
    }

    /**
     * 利用一维dp数组
     * @param weight
     * @param value
     */
    public static void getMaxValue1(int[] weight,int[] value,int N,int W){
        /**
         * 由上述二维dp可以发现，影响dp[i][j]的只有[i - 1]这一行的数据,因此可以用一维来代替
         * 其初始化不变
         * 递推公式：dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i])
         * 遍历顺序：
         * 需要注意，因为只有一维的数据，因此只能先遍历 i，再遍历j
         * 另外，影响dp[j]只有dp[j]左边的数据，如果dp[j]左边的数据被更新了，会影响正确的结果
         * 因此从右边开始遍历dp[j]，则不会提前更新到dp[j]左边的数据
         * 因此 j即背包容量的遍历顺序需要变为倒序！！！！！！！！
         */
        int[] dp = new int[W + 1];//为了能够访问dp[W]
        for (int i = 0; i < N; i++) {
            //背包容量必须倒序遍历 j的判断条件可以是 j >= weight[i]
            for (int j = W; j >= 0 ; j--) {
                if (i == 0){
                    dp[j] = j < weight[0] ? 0 : value[0];
                } else if (j == 0){
                    dp[j] = 0;
                } else {
//                    dp[j] = dp[j];
                    if (j - weight[i] >= 0){
                        dp[j] = Math.max(dp[j],dp[j - weight[i]] + value[i]);
                    }
                }
            }
        }
//        return dp[W];
        System.out.println(Arrays.toString(dp));
    }
}


